如果一個陣列中的任兩個元素是有排序的，是不是代表整個陣列就是排序好的？
這就是泡沫排序的想法。

如果我們想將一列數字由小到大排好，用泡沫排序的步驟是：

1. 兩個相鄰的數字相比，如果第二個比第一個小，兩個數字交換。
2. 從頭到尾任兩個數字都進行同樣操作，最後一個數字排序完成。
3. 除了最後一個數字外，再從頭開始進行相鄰數字比較。
4. 重複上述步驟直到所有數字都排序好。

舉例來說：
3, 6, 2, 7, 1, 4, 5
// 首先3, 6相比，不交換

3, 6, 2, 7, 1, 4, 5
// 6, 2相比，交換

3, 2, 6, 7, 1, 4, 5
// 6, 7 相比，不交換

3, 2, 6, 7, 1, 4, 5
// 7, 1 相比，交換

3, 2, 6, 1, 7, 4, 5
// 7, 4 相比，交換

3, 2, 6, 1, 4, 7, 5
// 7, 5 相比，交換

3, 2, 6, 1, 4, 5, 7
// 一輪比完後，最大的數字7會換到最後一個位置

可以看到在比較的過程，最大的數字碰到任何數字都會被往後交換，視覺上就像泡泡一樣浮到陣列的最末尾，所以才有泡沫排序這個名稱。如此一來，最後一個數字就算排序完成，所以下一輪的比較就不需要再操作最後一個數字。

泡沫排序跟選擇排序一樣，一次排好一個數字，每一輪要經過逐一比較才完成，所以它的執行時間一樣也是O(n²)。

正常來說，泡沫排序在最佳情況也會把所有元素比較一遍，不過如果是操作有序陣列，過程中不會有任何元素交換，所以我們可以增加一個條件，「如果沒有任何元素交換，排序結束」，這樣可以讓泡沫排序比較一遍就結束，等於最佳情況執行時間可以降到Ω(n)。

泡沫排序還有其他的變形，例如雞尾酒排序(cocktail shaker sort)。雞尾酒排序的特點是排序是雙向的，也就是會從第一個元素開始比較相鄰元素、排好末尾的數字，再從陣列末尾比較回來、排好第一個數字。以下是雞尾酒排序的示意圖：

圖片來源：維基百科

雖然這樣的雙向排序好像增進了一點點效能，它的平均執行時間仍然要O(n²)。整體來說，泡沫排序和雞尾酒排序等變化型仍然都算是非常慢的演算法。

接下來會寫到一些手法不同、效率更高的演算法。